import sortedcontainers


class LogSystem(object):

    def __init__(self):
        self.stack = sortedcontainers.SortedList()
        self.d = {'Year': 0, 'Month': 1, 'Day': 2, 'Hour': 3, 'Minute': 4, 'Second': 5}

    def put(self, id, timestamp):
        """
        :type id: int
        :type timestamp: str
        :rtype: None
        """
        self.stack.add((timestamp, id))

    def convert_start(self, s, granularity):
        s_list = s.split(':')
        index = self.d[granularity]
        for i in range(index + 1, 6):
            s_list[i] = '00'
        return ':'.join(s_list)

    def convert_end(self, s, granularity):
        s_list = s.split(':')
        index = self.d[granularity]
        for i in range(index + 1, 6):
            if i == 1:
                s_list[i] = '13'
            if i == 2:
                s_list[i] = '32'
            if i == 3:
                s_list[i] = '24'
            if i == 4:
                s_list[i] = '60'
            if i == 5:
                s_list[i] = '60'
        return ':'.join(s_list)

    def search_start(self, s):
        left_index = 0
        right_index = len(self.stack) - 1
        while left_index < right_index:
            mid_index = (left_index + right_index) // 2
            if self.stack[mid_index][0] == s:
                return mid_index
            else:
                if self.stack[mid_index][0] < s:
                    left_index = mid_index + 1
                else:
                    right_index = mid_index - 1
        if s <= self.stack[left_index][0]:
            return left_index
        else:
            return left_index + 1

    def search_end(self, s):
        left_index = 0
        right_index = len(self.stack) - 1
        while left_index < right_index:
            mid_index = (left_index + right_index) // 2
            if self.stack[mid_index][0] < s:
                left_index = mid_index + 1
            else:
                right_index = mid_index - 1
        if s < self.stack[left_index][0]:
            return left_index
        else:
            return left_index + 1

    def retrieve(self, start, end, granularity):
        """
        :type start: str
        :type end: str
        :type granularity: str
        :rtype: List[int]
        """
        if not self.stack:
            return []
        start = self.convert_start(start, granularity)
        end = self.convert_end(end, granularity)
        left_index = self.search_start(start)
        right_index = self.search_end(end)
        return [self.stack[i][1] for i in range(left_index, right_index)]

obj = LogSystem()
obj.put(1, "2017:01:01:23:59:59")
obj.put(2, "2017:01:01:22:59:59")
obj.put(3, "2016:01:01:00:00:00")
print(obj.retrieve("2016:01:01:01:01:01", "2017:01:01:23:00:00", "Year"))
print(obj.retrieve("2016:01:01:01:01:01", "2017:01:01:23:00:00", "Hour"))
